n=5000;
a=[4361,1,4216,1620,1548,146,3343,330,263,4996,4893,70,3053,833,579,4999,507,3890,547,3946,1895,4054,4443,2757,3022,3982,4314,2104,1303,142,2933,932,2195,3346,3591,1541,3757,4225,2547,4298,2883,1110,2283,548,1945,4770,331,4680,1235,4563,2570,1334,4683,2483,2695,4286,4932,87,1293,710,4801,145,2203,4828,1305,4862,105,1196,1212,1584,2281,2434,3599,3368,908,2890,165,4564,4163,2566,3391,228,3411,19,4670,4200,3796,3988,1112,74,3381,1732,4719,4989,2738,1566,1697,1923,1422,4162,2471,1656,4050,492,4685,2937,4570,338,3813,1424,2431,1307,3712,3863,2060,1861,4237,2622,1991,3113,3239,44,2974,1520,2561,1568,3309,60,2529,16,1691,1644,3833,353,2355,1426,4555,1188,3547,321,4369,2344,309,586,2936,891,563,3815,2227,2686,951,3244,3375,2360,4929,4266,1099,2948,1282,2620,2537,1606,1567,1440,4573,4524,1560,2478,4267,807,4015,2350,3325,1624,3250,2046,4881,918,72,925,3293,2262,2128,1376,902,686,1489,2885,3276,3940,3184,4045,3523,4065,3870,1729,4823,2090,2427,3497,4353,4173,211,4076,4087,948,3094,1939,729,4118,2399,218,2598,3984,2141,4908,2761,4206,875,4512,2234,930,2596,198,1166,7,1337,40,2893,2242,3177,4737,4456,488,3181,3546,4713,208,3656,1874,713,61,4429,1529,1682,2,2747,4483,9,2263,2426,1496,4874,2113,869,4283,4250,1374,1076,2417,1908,490,4748,47,2833,3746,3095,2116,741,31,2575,722,4614,3061,2681,4674,3748,1458,1055,2170,2453,4435,3843,4946,3480,3824,4260,3124,4898,2210,4761,4796,4227,2779,1474,2693,4002,3385,1294,1398,4114,4537,2673,92,3807,1982,3727,3335,774,1898,4273,163,2294,893,416,2996,3439,1562,1008,3872,4346,444,4484,2961,845,4241,71,3431,505,4710,4411,1574,4321,4938,1262,2648,2753,944,2455,4784,2773,4036,511,3055,2051,2037,4523,2373,2919,1543,4463,559,644,585,1242,503,3278,1352,2343,109,4809,1060,2367,3226,1709,1931,1573,1853,3986,1906,4151,3837,4947,460,3598,4340,1690,3191,3820,2517,2421,4315,477,4245,4424,4262,157,1998,318,2668,4198,2702,1719,3606,3765,3029,3173,3446,3420,3102,3441,378,861,4158,29,4130,2003,2891,4474,545,2979,742,3764,4889,4643,1514,2303,231,1683,1918,4755,698,129,1460,2441,501,1524,2197,1815,3407,570,1157,1948,3030,2397,1678,4194,1602,1504,361,4825,454,456,384,2691,4896,2841,3479,4625,3816,4604,3476,2657,1503,3932,467,4723,2270,1680,1860,4222,3688,2528,383,1542,3951,4538,144,2107,4675,4281,1607,3477,4011,2776,3281,1355,3844,2679,373,2096,4606,4221,1960,2198,3947,4974,3857,4413,866,1758,972,818,308,3804,3763,1239,1295,3467,578,1597,236,3079,4847,3259,1190,3907,3658,4817,2858,4102,1754,4661,806,3866,3221,4990,4527,2849,3747,4617,110,2959,514,4715,3448,1876,4136,1275,286,1700,1285,143,4860,2601,2721,3268,558,2836,2500,841,3070,115,998,4547,2946,1261,645,2467,1784,2150,2656,2293,138,2419,1420,1036,4829,4453,276,770,3894,3257,663,1735,4647,2741,3145,2975,484,4981,1093,2879,3112,4404,2804,2229,24,4550,3358,1443,860,3580,1534,857,3376,1492,3009,2771,581,2048,4416,3106,440,4995,4323,2387,763,3452,2298,1020,1070,4324,2255,3703,980,297,4476,1671,535,2772,4037,746,587,4213,2674,4833,4394,1557,97,3051,2708,1511,1635,4355,1642,1040,2402,4729,240,4133,4,618,768,2322,1970,4317,310,2142,3692,4977,2086,4492,3500,3458,25,4664,4778,2827,2330,2366,1984,4226,1078,2807,3087,1693,1549,907,1788,2024,3812,524,2245,2685,3840,1512,1032,2733,251,3071,401,4937,1122,4587,3105,455,3330,2325,3083,1245,2900,377,1932,3005,1200,3515,633,185,89,4331,3164,1953,3092,1383,1114,4635,3103,448,3021,1641,2368,1218,2204,4789,4012,255,3474,4072,81,4815,602,3657,974,2642,4473,1257,2548,2923,1670,2671,2514,3686,3227,4883,3147,4911,2663,1779,3345,1731,301,2451,4280,3520,4508,1241,2957,4771,3392,3081,462,549,32,827,2998,4157,777,3469,1075,813,595,3465,4578,3428,2826,3799,756,871,3864,2224,2542,4576,4068,3779,53,534,463,3315,1976,3511,4575,1692,2193,2400,3016,3829,904,2363,2268,761,480,1823,670,2282,2083,2070,305,3659,1244,4392,616,3749,1446,4746,544,3317,1827,536,3180,2154,215,3924,2474,3538,1627,1172,302,1845,795,2408,4804,1160,1038,4203,292,2092,3818,1764,4401,2463,1515,4179,3916,3294,4457,531,515,3826,832,3789,1209,3798,874,3889,1386,4365,1450,3402,533,4948,2006,2848,3742,1173,4790,4516,14,3336,2579,4965,2574,2644,69,4001,4458,1681,421,3423,541,4309,3283,1712,1332,4362,4150,420,4769,840,135,3348,3777,4611,2179,411,2180,2725,2490,2065,4178,2071,4212,3567,350,3817,3583,4104,1202,122,1988,3761,1018,1388,723,3308,1296,1345,303,4783,269,3701,2489,2698,1904,2520,4408,3628,3992,4370,4797,4496,4100,1522,2178,3575,4686,3351,890,4819,4553,3232,3096,2448,1751,4753,608,3641,1855,916,4992,1423,39,3835,2534,786,1724,4113,662,2469,811,2057,655,3913,73,123,1887,175,965,3875,4994,1965,4304,2122,173,1625,4554,1071,642,2183,1469,2462,1083,1430,3270,3222,3314,3858,85,4475,2925,2578,431,2706,880,609,3366,4107,801,2345,2072,3516,4851,3352,929,3679,781,2909,1268,4439,678,4631,289,1193,2704,2256,1539,4877,3736,4581,865,465,947,3930,917,3600,2700,3038,120,3823,1204,2956,3272,36,4536,4899,3674,4787,940,381,1814,3503,3080,1471,4639,1320,2906,1695,2250,2913,4502,3690,2507,1711,1884,388,4032,4888,810,2323,3245,3713,171,3607,639,4051,201,4244,878,102,4892,1174,366,2410,3544,2155,2053,2983,2735,2085,3013,1354,461,2947,3948,4953,1718,2748,1842,3165,4960,3911,1501,4766,372,4351,3128,2106,133,1849,4383,3745,1537,114,1442,93,4600,4186,610,1144,4067,676,3574,3596,410,2109,4807,3069,106,3886,3622,2952,1993,3266,2274,3790,3006,3473,1286,1253,656,1171,4754,941,469,1892,3792,3670,897,2895,732,2801,299,3139,1240,747,1610,589,1772,2019,1109,2818,4478,3794,197,4405,4071,3171,4183,3340,627,4029,1082,4073,3755,3399,1246,3561,2955,3706,2014,1859,1086,4430,915,1067,4975,2126,2177,900,2124,1818,4528,649,2216,2001,348,2219,700,2802,3744,1778,1094,738,1418,2173,402,2318,959,4846,4234,1668,1358,1655,4319,3961,2749,758,1031,3788,335,3432,2694,2819,4308,4954,3236,2271,1177,3672,3782,1561,867,1234,1938,3952,3922,2246,1477,1223,4128,2446,147,3306,4612,4166,2188,1106,3896,101,200,4208,3091,2711,4035,4486,3116,312,399,3900,573,4145,4494,327,2746,599,2786,3654,3834,3299,4138,1705,4574,4645,2482,4326,2504,3677,329,3697,2120,2247,3839,2034,1935,3367,754,1980,3304,230,227,3545,699,242,41,3363,3566,3161,4334,3995,1326,458,103,2191,34,971,3,1713,4160,2646,4350,1364,4767,614,4432,4956,718,876,1072,2775,352,3297,4171,3169,1902,702,1646,4830,1035,2334,2760,4044,205,2889,2954,449,1822,111,2280,1003,1919,1052,2825,1801,2971,3680,1550,1306,2370,1298,272,4196,112,895,4777,2795,1487,3015,1340,445,1167,3960,78,3897,4841,4793,1516,1817,603,1181,969,4959,2009,2319,2129,4579,1195,1431,936,2852,2643,892,202,2898,166,1742,4602,3223,3088,4800,787,4139,3138,1575,1720,1701,597,1466,1338,4295,209,334,4726,345,4302,3633,667,4895,1382,2539,83,4003,2098,1259,1600,2081,2633,4251,928,1150,1790,3570,497,3559,1473,1125,3119,3533,2032,3175,3774,4772,4942,2632,4568,2371,3456,2755,4916,3645,652,1957,4360,924,311,1077,712,3987,2447,592,284,1198,3468,4636,58,1832,3805,521,1476,1531,281,4596,4872,2390,1384,2182,2788,525,1806,3086,764,4445,2484,2882,1645,1922,2796,1816,755,3093,1619,2720,364,1146,86,4663,3998,2977,1098,1051,1552,2873,596,4944,1130,3166,2328,1059,2910,375,985,4743,679,1907,1555,2594,4682,4042,1329,1229,496,3451,1136,225,2840,1792,3492,4717,3726,4917,1463,3303,1799,582,424,2031,137,583,1187,1117,835,4197,914,594,519,6,1741,300,2038,3990,223,3063,4658,3524,4742,2865,4064,4277,1944,4135,3284,4725,2926,3554,2016,3643,2168,2649,62,2855,4248,4696,2821,3012,641,3721,1001,2137,912,847,1576,3883,553,222,1688,3646,2206,3683,2822,2875,2259,695,2586,2097,1371,4215,706,697,2376,3291,848,2039,4406,4422,2877,314,4398,2074,2729,2589,3634,203,1928,2608,1782,1478,4549,494,1432,1971,3148,4991,4085,4343,877,4653,622,993,3682,638,2382,2970,4293,4970,4986,4088,3410,3404,1331,1194,1118,43,2751,3504,2662,4831,921,241,3750,4733,1540,1325,1289,3540,1517,2995,1154,4837,1599,125,186,2764,1197,1368,1684,55,2874,2335,2194,337,3925,79,3279,1990,1449,4652,1756,1277,851,3388,3384,3822,2886,2392,2225,2551,3668,271,4188,2443,2658,2880,474,3483,3879,3871,3146,3715,141,3584,905,4481,1614,3075,4279,4530,2866,510,3117,4341,2897,1143,2004,4144,4016,3034,3359,3787,3611,1226,4632,3481,3793,277,392,901,839,4585,4498,4122,4957,1120,2864,1862,3859,4971,600,1672,247,2665,2680,4117,2672,415,1216,4791,1248,3846,3412,4923,518,3640,556,3225,217,2597,634,557,2391,2573,4199,4543,1639,360,155,966,2459,4712,1208,3285,3825,650,1605,3024,1148,3860,657,3513,3154,3603,1572,4047,2538,30,2284,224,4590,2742,537,1272,1434,995,46,2160,3716,3853,2744,33,1301,4303,629,1510,156,2030,3211,2279,2731,4560,2709,3797,181,3241,4803,3667,4597,580,127,2233,1375,794,2230,2158,2022,3389,3850,798,264,3501,778,4297,719,38,4642,4785,665,4395,2264,3203,326,2021,2480,3027,452,2165,1532,1992,4968,2563,1896,3885,4192,4013,2862,3664,1493,879,4567,1111,1317,4000,3510,4703,677,4195,4638,4927,2834,2641,2437,1604,1451,2359,2792,2169,296,3379,4419,4834,4124,3605,1536,2213,313,4738,4757,2192,432,1888,1759,4288,3888,1407,3490,4017,1664,3576,1201,1851,2758,3903,3442,4826,161,1872,4299,2108,1203,4336,1147,4489,4099,2512,2199,1598,3132,1373,4716,3421,1178,802,436,214,4488,2844,4328,4399,1236,1798,4024,3832,283,1786,1022,4207,2942,2982,1673,4033,132,4630,1456,4337,1546,3298,2838,3361,3198,1528,3543,4415,4795,1819,4420,796,3848,3950,1915,3033,3074,2991,4740,4021,10,407,2525,3246,2058,3740,981,830,1087,1158,3218,736,426,2278,884,3243,408,4446,1638,3637,1685,2669,705,4261,1824,991,625,653,1626,2737,4421,3989,4708,2717,188,1847,735,1825,4541,3296,4380,4402,164,2726,1891,427,1207,3445,4906,2273,2181,2157,1676,3062,2093,2139,4515,3121,2337,4941,27,1844,3696,4061,1377,1880,1858,3579,1897,3035,3956,1042,4964,4951,3484,4389,2172,4105,3876,1399,1995,4485,1185,2265,4676,206,3733,3771,3970,1481,2778,1321,4455,3356,4236,3581,349,4747,376,4461,35,280,3350,2339,1401,3920,367,1913,3120,4824,1926,3201,2125,1280,4233,3347,1385,1679,1582,532,2510,4558,3802,3136,1559,526,406,572,1126,2787,4142,3238,1006,1409,2918,1826,153,2499,3387,569,3766,3444,1068,4403,99,1882,4441,4919,1583,4228,4039,2502,3892,2286,2336,2297,682,3127,1217,4285,864,2101,3760,2313,1316,500,4858,2013,2524,1805,1004,3354,1156,4427,1513,4493,1053,1107,2481,824,2546,1941,4426,1966,2616,180,2813,4272,1369,2790,2492,3290,803,4009,598,3332,2103,1411,766,4513,4081,952,2159,872,3156,1105,909,3425,2468,3800,2028,4356,3319,3648,561,3301,1675,67,1297,4218,2588,4444,1137,4609,1389,4580,4928,1309,2076,1930,2135,4469,370,498,4263,2497,1135,3331,2938,3741,1615,2349,2084,491,54,2823,2364,1265,1911,4278,923,149,2678,3532,2329,2044,1091,4465,3909,3666,148,2555,433,4732,673,4177,1714,1079,593,2439,567,23,2763,1587,4677,3661,4500,1578,4472,4211,1065,3305,400,3090,4004,3273,4646,1243,2703,4605,1034,3043,1323,3609,4792,1854,4300,2660,1164,3041,1233,4934,4544,2477,842,4905,2501,4451,626,2372,3786,3556,2327,4539,3944,647,2054,887,323,2310,1812,3882,886,3133,260,3369,3220,4423,2611,4768,822,3919,1622,1141,882,1300,274,2163,42,1128,1757,3210,1453,1694,483,2591,419,3938,3636,4870,1327,1050,1057,2340,3422,275,3714,4052,797,3065,4240,4143,2082,2275,2716,1507,1394,4290,987,4961,1661,4409,604,4108,1789,409,3522,4059,530,4871,1586,3085,3231,3370,1591,2251,2147,3098,4090,3964,2052,3129,1406,4780,2526,3841,1310,666,1972,4668,3624,4918,4239,1467,3671,1405,717,3612,546,789,2430,804,776,4229,2043,3983,3976,343,3555,3014,1429,4077,2162,2907,3560,4903,2342,4127,4622,1062,560,4813,1247,2033,1101,2211,28,1271,1410,2420,771,4765,344,1934,1436,207,4798,4979,1104,4978,1224,1669,1372,1921,187,3959,1041,4782,1760,4269,1363,379,2148,3182,2600,4519,2025,3049,2276,1028,1184,1048,528,3178,1813,4691,3163,1651,1649,4312,3008,3489,2241,751,588,355,2730,2953,1232,4623,1985,1717,4436,4958,167,4598,3521,3322,2832,1837,3534,4079,2964,3153,3698,1392,1322,4407,4656,4149,2932,4633,3212,931,4374,3137,3862,1937,4546,2684,1210,2300,1630,3134,3010,4812,808,3979,3219,3915,1766,470,4452,3189,2285,1380,3949,3759,2257,1278,1841,4372,3040,3739,3996,2683,150,4131,2860,2811,834,2912,245,3663,4618,294,4252,4005,475,1667,962,4949,3602,3881,640,2231,709,393,2714,4651,459,2707,743,2999,3050,2200,2316,4641,788,2777,1102,4287,52,4082,4284,244,229,4354,554,4687,4028,4301,100,2602,3548,3179,429,3635,2752,2799,1353,1996,258,2075,216,2945,1381,2696,2894,2846,1793,4477,1284,4201,701,413,1404,1287,3691,4110,199,3435,955,4305,4594,3676,4191,4181,2816,1108,3620,1408,4190,4487,1940,4193,2132,1061,4447,4329,4031,3289,740,1797,177,4069,3552,4709,1211,4189,3141,2972,1250,3234,1912,809,2899,4902,3638,3647,1186,4698,324,4637,2728,4219,1603,2655,482,539,784,2881,291,1750,1069,3811,4257,2433,4238,3188,1056,4997,3880,4887,1698,4739,1472,2115,606,3383,4671,2645,386,453,2236,3905,1149,2239,1252,4101,988,446,2820,3494,3206,3621,4749,1989,984,235,615,3472,1783,3360,4533,359,3424,1066,2595,3702,4092,2831,3144,1699,2922,3652,339,3831,4063,4624,2017,3073,660,2628,1336,2146,3380,1866,2201,3572,1632,382,4879,8,2214,441,3498,2287,1182,3508,2080,4325,3286,3326,2404,2479,753,2577,2398,4521,3929,3341,1802,3514,4231,3535,4438,1413,3047,2850,3571,3433,816,4274,3725,4112,2623,3064,2401,3836,1740,737,4884,2713,3632,508,960,3447,703,4364,22,4470,1044,1864,4532,4852,486,4414,2440,1848,3252,1127,4026,3100,4506,4382,4861,2705,2587,3851,4583,4223,4762,2252,2984,4897,3838,4520,295,1119,1527,3618,2701,4169,4480,1708,108,4147,3078,3059,3152,4545,4962,304,613,3237,1047,4322,220,1769,2385,3912,2509,4607,2810,1994,1015,4882,178,3208,1831,3877,2667,4504,828,3418,4864,374,266,1795,287,2207,728,1291,805,1749,3902,4705,397,4939,2522,1901,4460,2809,605,1951,1820,3529,3205,4378,1653,4070,1658,4619,3954,3662,1361,4018,253,999,3541,4849,1654,4057,450,1977,4763,3910,391,4119,2690,4998,2153,1170,1870,4209,4788,3004,3076,3617,4730,3437,692,1402,4873,3011,1140,734,396,3295,3406,1439,1875,493,4449,2333,825,1335,2867,575,4053,3256,4396,182,1927,812,499,1564,3758,1115,3720,2002,1613,3623,4985,4854,2055,4247,2383,340,3650,3972,2272,2940,4256,675,1304,1103,2842,4926,757,3400,3018,4140,2138,4759,3248,2088,1084,234,4254,3253,1080,3159,538,3849,1808,1010,2186,693,3200,1090,1192,4921,4379,1723,1290,4548,3558,3142,2762,1505,1258,2460,2531,2856,316,793,1828,1636,3962,3528,3104,4613,4706,1843,2503,1276,2794,479,1768,1421,267,3287,1657,356,306,646,2311,76,2692,4363,2449,3377,2491,576,1547,1438,4810,2413,319,4697,982,119,3781,4020,727,2592,95,336,1933,1097,1428,4950,919,3414,3032,1155,212,3565,2543,3118,4132,91,3072,1973,2847,4969,3589,4282,648,502,2868,151,1046,945,152,4535,3975,4232,1748,3819,4342,2976,2005,1168,689,3215,910,3933,1213,252,3264,1054,2171,4123,4588,3695,1810,1433,2664,4886,2380,523,1726,4167,3230,1191,1215,953,1495,4648,2759,1328,926,4344,3186,696,279,3847,1830,2040,4681,4182,3329,4701,1879,1299,4125,1776,2379,1479,1721,437,3536,3874,249,4014,1393,162,1596,3025,190,1448,136,4115,3288,1162,1482,772,1100,160,1594,2164,1728,3806,325,4616,466,989,849,495,1677,3023,3084,3310,354,933,15,1315,949,3324,4758,4679,2557,1946,1021,3190,1535,1025,750,1279,3364,2301,4878,3110,3530,4904,3499,3131,221,1974,3333,2320,2603,3235,2654,4875,2515,3386,4750,3374,3738,2386,2871,4925,4462,2815,584,4751,1730,725,564,4217,2535,4562,3056,380,4660,2077,4352,57,2338,730,2951,3217,179,863,3842,2782,2943,4335,96,4129,56,183,1894,226,2495,2304,3525,1687,2781,2927,1064,2830,1221,4700,1390,3353,1660,4540,3077,1762,2878,425,1737,1686,1962,4667,2374,4863,964,3475,1292,1370,4049,94,844,3991,3756,2324,4010,1910,883,873,4270,4471,1947,239,2149,4935,50,2584,1498,3036,2378,1883,4808,3261,2653,1461,2934,3681,979,423,4294,1444,2911,3068,624,2174,2699,2314,1165,3590,552,3887,522,4349,2308,1903,3526,3935,3734,1260,64,2935,850,3917,49,2613,967,4626,2610,773,1308,2026,1975,4634,3060,4621,4154,958,4066,2530,1419,831,2167,1929,577,1554,733,3649,2442,635,1348,1585,4756,791,3114,3162,2560,2803,4774,2422,2583,664,3196,3209,4529,2143,1571,98,977,4704,529,1007,2121,1417,3401,4094,607,1400,4291,4271,2929,1785,3229,473,2269,4689,3280,4552,3007,721,4046,3493,2036,920,3464,2723,1917,3125,4972,2423,1254,2357,4644,4083,176,3307,3176,3966,2465,2133,2486,4669,4764,516,767,1943,1631,417,1267,2061,2429,3158,2388,4821,2870,3496,3207,2428,1716,2432,2354,2258,3660,2521,1523,3957,3172,2765,2712,3251,2571,2558,2454,3292,4126,3260,935,2625,4417,4339,3722,2190,630,4745,3644,1899,4249,2473,2056,4387,4522,2609,3963,4230,487,4640,1412,4482,2291,3123,3108,2576,2403,1739,3631,3312,2457,2409,565,3926,4224,3419,3953,2805,443,1791,4318,113,1519,994,4448,4827,4599,4781,889,4988,2921,1580,2407,3512,520,783,775,4467,4006,1138,2769,4210,2045,26,3417,3115,898,3058,4095,2562,4720,3174,1954,1095,4511,3629,2184,404,1311,4468,2100,464,4084,2112,780,1533,256,2089,3608,3614,1189,4649,2020,4235,3783,3339,1650,4684,1366,4501,1914,1983,2496,3737,2532,1131,1647,2756,2008,4375,2638,690,1767,2487,4259,1387,369,1365,1347,3732,3066,4397,4152,2817,2677,4093,715,4666,2166,3355,2136,2962,4091,4185,1752,4620,3342,2238,107,1871,2396,2789,1952,68,1356,4019,617,2990,4040,4390,637,4608,2967,4976,4727,1357,1273,3769,1263,4097,1863,1030,3564,4437,3772,950,903,3978,471,3505,1508,438,238,3486,2205,4204,4316,2249,3199,422,1180,3627,4043,1967,1151,2073,2277,351,2362,643,1225,3313,3101,3895,2066,2978,1465,1179,3878,4993,2023,1457,2519,659,3588,4693,2472,4434,1024,1220,1037,2202,3026,1344,4060,3553,3183,3394,1545,2118,232,4517,4431,2185,4894,37,4141,4391,1378,2436,800,2930,3852,957,1640,2196,2768,3927,2493,4327,2321,3751,1569,1027,2381,4601,3923,4967,268,2966,2260,2767,4161,2315,963,512,1092,3028,2994,4491,4924,3867,4702,3542,4098,4531,3626,3194,489,1800,3466,3685,2888,1893,792,2624,631,4966,4385,1251,4156,2305,2569,2661,819,3784,4202,4479,2564,4987,3192,1761,1425,2348,2289,3735,790,4466,1199,685,2604,3455,2697,3993,1256,1857,684,270,3427,4559,1414,1794,927,2605,2556,899,2152,922,3557,1441,2094,943,623,2226,75,1961,3601,1238,3397,3507,126,1608,2615,2050,654,1269,632,1556,3517,680,2341,1736,1592,2232,2901,2675,2130,3430,2892,4509,4900,4025,398,4464,765,2687,4714,2244,1878,3365,2884,4952,2222,2123,3097,3323,1468,1869,169,3941,4371,4842,1026,868,3491,2145,4694,1349,4376,2438,976,385,720,3454,2552,2312,3808,2541,1925,4811,4593,3980,288,854,2317,1634,1590,3502,174,1715,371,885,1437,2069,3810,658,3704,442,1777,4258,4332,4855,2924,2908,4246,1023,2719,1525,1811,4818,1734,1121,2059,782,4450,4373,3655,1924,2590,2416,4440,3918,3891,4311,3216,4187,4503,1836,2851,4056,1829,3099,457,5000,2208,2651,1509,66,4078,990,4843,996,4041,4023,2739,4794,1096,2750,3801,1074,1689,3785,1484,447,213,4915,3240,1856,3908,1979,2876,3568,2905,4497,1565,562,1497,4386,4802,2476,412,3233,4586,478,3770,1502,2814,1163,2243,2599,4822,4913,118,3616,4786,278,317,681,2395,4425,2986,1333,1544,504,2722,2618,4505,4615,2011,3684,669,1455,2516,3269,2505,3202,2307,4955,4912,749,4572,2292,2568,3495,906,3942,542,2835,3344,1312,3699,2288,4096,2670,911,2920,3320,1959,1852,3449,4890,2218,942,2853,2223,320,1397,2727,65,1360,1063,3753,820,3531,726,428,4499,2859,2861,140,342,716,714,2393,543,2237,3302,3893,2793,3415,4366,3413,3170,2715,3550,2498,2992,2365,3003,2346,3300,4310,3678,1346,3187,3204,1753,3551,3337,2351,3067,1936,128,2800,387,3193,2630,1579,1986,2488,2791,2406,1796,3382,2806,2553,3906,3255,1500,4940,3901,3689,1488,2710,3854,1804,117,3928,357,1039,2743,233,724,4320,3861,3974,4657,3267,1725,3213,3898,1314,4838,3985,2567,1169,3593,3482,4148,3020,1781,4526,394,4885,1330,2915,4930,2523,1563,4255,3031,2636,4089,1132,3687,4844,195,2634,1881,2736,1780,1807,3585,4514,3619,1969,4933,3997,3462,2843,1459,3729,4859,3537,290,3958,2824,2029,1886,2215,210,48,3228,1012,2593,3914,2785,2175,2161,3487,1821,2949,3334,2676,4008,1319,815,4711,2212,4595,2958,1909,1617,517,1133,3539,4220,2415,1009,1486,1663,2612,4180,2969,3969,1318,3718,4936,3157,2511,4880,1073,3440,3140,84,1916,2450,104,2582,2581,2456,1249,2941,4814,975,4736,2261,1774,4654,2902,3349,1963,1722,4901,3768,1890,3731,3242,3195,4628,1230,2904,3977,3921,4377,3730,3828,3562,2513,3265,2087,3488,4153,2666,3752,2770,2766,2554,2235,1840,219,4868,2627,1958,2228,418,3254,2156,3019,1839,2652,2544,4433,4836,2425,3436,2963,4848,823,1775,2035,4367,574,527,90,4561,139,2508,3776,3673,1618,2960,4034,1551,1809,3130,1490,4718,4922,434,3625,1159,435,3037,651,3669,4832,2042,5,708,2347,3943,4776,4592,3724,2091,2863,2356,390,4779,3151,2010,1868,2220,3700,3135,1987,838,3463,3214,158,4775,4175,2944,3316,1452,4907,196,1403,970,2295,4393,4973,3405,1553,2015,1205,1085,2290,4525,2041,4910,2151,3045,154,4707,4134,4866,4348,59,3549,3258,4865,2267,2621,938,3398,1266,2533,4357,1367,968,4565,1747,4914,293,2375,2659,3001,4109,250,414,4490,2688,3338,4799,4155,2047,2353,3416,3262,4174,4214,1589,4744,826,1475,3403,131,11,4582,4307,3791,2299,3973,362,2619,3999,3409,4840,2559,2067,687,12,3372,2063,745,992,1494,1616,4551,1049,4428,694,986,2928,1014,2309,130,2254,2647,2302,3778,4027,3592,611,2903,1183,1648,2797,568,3578,2506,3569,4292,3275,1628,2931,2626,2572,852,2988,913,571,591,2724,1470,814,4121,1570,3586,403,2187,2965,1145,1019,4672,2131,3693,3155,4678,2631,1703,4347,3780,881,2639,3485,3573,4850,2896,4058,1665,2384,2018,3046,3168,4007,1652,3373,3378,2798,485,1746,2689,1659,870,4876,3328,3743,711,829,1696,2114,315,1395,2989,2064,3044,3453,1558,193,1175,4920,3506,2540,481,3429,20,51,1955,3362,1339,4566,3321,191,2997,506,3937,4943,748,704,601,1956,1281,1045,1612,4556,1237,2411,3089,2650,1674,1464,4086,3054,1350,4659,3470,1581,430,1342,2828,3717,2394,282,4074,1415,3396,3393,3830,3509,2682,2296,261,1710,3057,3936,4358,439,1222,246,769,2369,3274,1743,2854,3082,509,3865,1081,4655,262,2007,3167,3773,4400,1773,2754,759,1088,2580,752,2549,1942,3710,817,1964,237,1491,2914,4853,2078,1577,389,2079,1997,2916,88,1176,4164,3017,2950,3723,688,4111,2536,2445,620,121,3708,1283,3630,13,285,254,2917,4734,4867,956,3318,4571,671,2326,4534,3965,2189,2361,4839,1379,2452,3160,4276,3694,3968,2518,2614,4724,4760,4699,18,4629,3000,2617,2981,4022,4313,3711,1362,1391,862,4869,45,555,1142,1978,1611,1161,3052,1521,888,4577,1905,2774,4442,4345,843,2105,3461,3563,3994,2783,3814,961,189,4242,3527,731,1324,3615,328,674,2839,2412,3665,341,3705,3827,1900,1454,3048,760,1000,3653,4980,1885,1662,3478,2872,2527,1835,1733,2414,4172,1744,4075,4388,3457,3577,2068,1601,1867,1846,4835,837,3471,184,4137,896,2780,3282,739,2405,4662,540,3327,3904,4289,3899,4459,1152,997,4368,2985,4159,1833,4168,3271,405,1351,1089,3149,799,1359,3931,4731,3754,2377,973,3594,134,1518,4982,2637,3438,3122,192,3719,4170,858,4518,1483,3595,1704,80,1538,4146,3395,3856,2808,619,2732,628,1526,346,707,2635,243,2458,4030,1228,4243,4384,116,4412,2424,4106,3002,939,3434,1445,1313,4909,4627,2266,4306,2095,63,856,1124,954,1506,3519,1968,4945,2973,368,4120,168,3111,612,3587,4176,779,3357,2027,2209,1002,4542,1593,259,3868,2134,4589,3518,4557,395,1011,3775,1343,2217,1005,4410,1999,3390,3955,3762,3869,785,2461,3109,1920,451,2475,3981,3613,4165,1787,3311,4963,2240,170,332,2127,1803,894,3042,3107,4507,1153,2784,3582,4816,3934,1288,4584,1206,4931,3426,4381,1396,4359,307,1499,472,1755,4752,4983,4330,1637,4692,3971,3845,4820,2968,4845,1480,4055,17,1623,2993,3185,1707,4806,4253,358,859,4296,3821,265,4184,3803,3728,4510,1770,2102,1727,1950,3642,4673,3651,566,978,2144,621,4688,2389,3939,1139,550,2494,846,172,1850,273,1633,636,4495,2829,2629,194,4650,2306,934,1738,3639,1889,2466,4080,3247,2470,1629,2565,2435,3143,363,3855,77,2640,1017,2331,744,2939,3277,4264,257,1702,3039,2117,4856,2607,683,2606,691,124,4984,3809,3610,4773,1763,4338,1219,4454,1302,1123,4857,1227,1588,3459,3450,2012,4275,1043,1255,983,853,468,2111,551,4418,1621,2545,4665,204,1029,333,322,3675,2000,1530,3263,2845,2176,1609,672,762,1595,2745,2857,4116,855,1765,4205,2887,2099,1838,1771,4048,1013,298,2734,821,2352,2464,4569,2980,1231,1865,4103,2253,248,4603,1462,1270,82,1416,2332,3873,1706,937,1274,1877,2221,3967,1447,3707,1485,1129,2812,4721,1214,365,2110,4333,2248,668,2485,1016,2987,3408,2718,1134,513,3150,3224,4695,1745,2869,2418,159,2740,4735,1949,4891,4690,2550,4062,2049,4268,3249,2062,4741,4038,347,3795,1981,1834,946,1666,1341,661,3126,3884,4591,590,4722,1058,4610,1113,4728,2585,3443,1643,3371,3945,3197,1116,2140,3460,2358,476,2119,2444,1873,1264,836,3597,2837,21,1033,1435,3709,3604,1427,4265,4805,3767];
b=[3781,4702,2330,2415,4269,720,3892,4519,1233,3535,2587,454,473,44,87,620,557,124,3265,17,1482,3857,2139,1302,3439,3741,3797,668,2827,4355,3616,95,4179,2839,2906,1241,4213,281,2528,860,2361,4017,3339,2432,647,2224,4900,367,3173,638,1076,2403,47,4446,3063,2803,4278,1244,3155,752,3998,412,1072,4546,2345,1293,2099,1121,1749,450,3203,3142,4059,10,911,1147,3571,3573,4575,4080,2624,2023,1475,3615,4258,576,1507,3434,1650,2764,4310,3860,2735,1093,2462,1926,3094,542,155,4415,2824,1458,2365,352,3038,2172,2591,9,2833,1620,2760,2538,2130,1743,4345,1154,1922,3454,1820,3028,4975,3048,3685,3493,1044,804,2089,1992,3283,2434,527,968,2974,3107,1473,546,2531,3002,1852,1830,1439,578,723,1404,1020,1070,3306,519,3878,468,1286,1734,3503,294,4328,1196,3977,1462,103,1477,3047,4467,3798,4822,128,3756,4538,1638,2300,605,4458,4113,2611,1508,3897,234,1697,1113,2590,1480,4751,2101,2219,3397,4054,2909,1606,1970,4761,972,4262,2876,2692,2926,1313,4740,2378,470,3297,2686,881,628,1255,1298,4038,1176,3808,3604,2511,2808,4303,1545,3191,2959,4516,4622,511,1946,2747,4123,2000,1568,3943,150,2633,1276,510,3595,3013,41,3314,1530,3867,410,3979,3036,3393,4711,694,1953,4703,3964,2069,4960,492,548,1116,2176,3237,30,4760,33,4338,1684,482,832,4851,157,2179,1909,4134,407,3004,2304,4804,1589,318,3729,1984,2009,866,3441,1066,1884,4731,1266,1870,4156,3747,1968,3189,2502,4013,4224,4323,3089,290,1905,3255,3826,1602,358,2793,326,3730,3011,4743,1456,434,3102,4155,3856,4599,1130,2685,1139,2104,172,770,810,264,1451,4369,3918,4004,3724,3377,2976,757,886,4990,3370,2746,3248,4334,1584,181,292,4844,110,2943,3952,954,4584,558,3509,4276,2705,2152,1019,1877,2400,2008,1039,2683,3406,2574,617,3769,414,1079,3695,3396,3719,1429,3575,3033,1960,1599,1344,4225,23,2156,653,2476,2680,3364,996,4894,329,4220,1872,1630,3467,4455,1299,4768,3578,4695,627,3273,1469,2631,4670,4335,2251,1319,880,2333,26,3256,1392,1793,4163,3591,3271,2318,4324,739,2027,4412,4539,4264,1190,3638,1419,3704,684,1876,1364,1045,1615,2048,4236,2884,432,3959,362,1983,2762,4998,2552,2423,2004,4154,4260,1159,852,1999,3290,1395,398,2356,579,2575,934,100,2728,4135,413,3174,422,924,774,3870,3514,3143,1828,2411,1563,4626,3654,4399,4089,1769,2253,3957,404,4238,802,2453,2380,1867,4021,1998,4566,2951,882,3849,3969,890,1467,1988,3483,1847,245,3372,2260,1612,299,302,1012,1735,2446,768,4079,4839,142,4772,3651,2709,483,1944,2570,4044,2038,1013,1938,1309,1384,2151,291,3668,2440,4831,2478,1948,3876,3624,1918,776,3564,4281,3220,4623,3566,925,3725,824,3457,2133,3224,3502,1653,1551,4978,3311,255,3238,624,4266,598,4289,4122,1493,1756,2385,758,2278,792,1441,1488,1409,68,2722,262,3627,4024,3653,4221,2424,3177,4291,4299,1413,226,2637,307,4667,836,4765,2096,3403,2673,2993,75,1287,259,2189,1437,3234,325,4452,102,4118,1969,2753,1879,3751,2544,4688,3039,4234,5000,3291,3414,3027,2634,4305,1858,1578,3499,1270,923,2495,4464,522,3898,2487,4422,4736,387,3873,4240,3749,316,4637,1898,2643,4103,4125,105,4181,4016,4283,1249,3833,4920,4679,1170,2429,874,2420,3332,4057,406,4586,2642,930,2710,1680,1865,572,2836,523,678,3532,120,2470,3461,3459,1374,4686,3866,2097,4836,2513,38,2258,2618,260,3853,3213,4814,3456,3580,3229,4150,652,581,2559,338,4832,710,1929,588,1924,3909,4275,2750,3035,29,3362,685,2146,4888,2067,507,920,2379,4011,364,2398,2193,1195,403,4882,423,2283,3988,1943,825,4774,4036,1239,4889,3497,3525,3041,1798,1569,420,4779,459,3705,1704,4747,1127,976,195,1812,2442,4159,3750,3614,2960,4962,1355,1157,2238,3791,3482,955,2468,2604,2357,3469,660,2962,4932,2196,167,2013,1765,800,2437,4084,3678,4420,4927,1218,4453,1452,488,3543,711,3061,37,3996,1954,1331,1934,4373,3844,4138,4248,3739,3834,3302,3323,3141,4397,4895,204,2807,2338,1471,2055,2074,221,402,4432,637,62,2995,525,3772,1512,850,306,4246,786,2194,1426,2145,51,3738,117,3963,1383,3506,2043,4689,3348,4472,4200,1129,2264,4614,2745,2001,3076,3095,780,160,2874,3962,4372,2945,765,2890,748,4256,2499,952,857,481,4540,208,4663,2036,751,2092,1466,2663,4300,2990,3492,4618,2148,4073,784,2490,368,3171,1327,3129,3289,74,681,1807,2164,222,3462,3555,4363,3823,820,4861,1810,2963,1018,4111,2409,1685,4940,735,2775,3728,504,3836,4795,2515,107,3763,1074,3951,3609,4191,2024,3679,147,3901,2410,145,3599,4572,4028,1791,1804,4170,2198,4162,649,3902,4936,3093,3643,207,445,2702,2014,1742,1136,4951,2678,3736,1690,4825,4532,583,4965,73,3253,1060,3188,4717,90,4463,4969,3425,1712,4885,3742,2697,126,846,1180,4343,477,3045,3773,3764,4562,4208,3858,731,1149,1031,3292,4756,2237,43,4267,2288,2656,1378,2337,3192,4215,4666,719,4993,859,4413,3776,813,809,3922,509,4321,1636,1000,3299,1274,2082,4897,3816,4750,953,1021,2327,61,3762,4950,305,2905,912,734,4417,1415,673,3629,3298,1682,365,4401,456,4018,2534,3123,980,4593,3417,3091,3561,884,2150,2640,356,1768,906,2281,2457,3373,2220,2352,763,705,1500,847,340,4292,895,3366,2480,2526,357,3707,570,2811,1425,2597,1048,4348,2713,332,1248,270,814,3261,462,1232,1554,3717,4798,3146,3805,3157,1701,4392,4716,4176,2138,951,3847,4007,2228,2103,2949,4658,486,4265,1192,3193,2441,2168,4603,2782,309,3050,382,3915,2010,1955,2619,2989,485,1956,4268,70,926,919,769,3992,2606,2376,547,3125,54,4728,756,372,328,4428,2301,4845,322,2232,493,3925,1646,1785,343,4613,2771,1503,478,1169,3610,1024,612,3852,2040,1373,2206,1981,1055,3531,2828,949,2336,4400,4233,2035,4066,2113,241,1283,718,1259,499,3563,3452,4314,4358,1333,4813,3584,1372,2081,4074,3505,3084,2061,4065,2599,4508,3788,4980,4026,3568,2644,1303,1432,3879,111,217,3841,324,371,59,4403,2452,268,883,2041,3330,1285,1300,1794,1087,3124,917,1158,1782,3019,732,1164,2203,2404,3516,1057,3103,2175,1090,4581,1440,3429,1908,4727,4005,3978,4948,1194,4821,363,3249,3589,1444,998,1729,1264,2217,3722,1592,1106,1382,3233,376,4591,2329,3547,3184,1683,3740,3684,3840,764,1766,4045,114,3138,2668,4069,1122,4555,81,4244,1588,4661,3489,1489,4902,3947,1774,3635,3069,1168,1892,1207,1581,4359,1141,3587,4311,3995,3034,4878,2783,2205,3432,1901,1314,1664,1047,3787,936,1135,1238,1447,83,1491,4100,333,1574,1871,1150,3758,4484,3691,851,1050,4374,4857,1610,2003,796,231,3126,1220,233,2497,4550,1590,223,199,5,229,278,3883,2711,528,2042,1947,3639,232,889,4770,3698,4833,439,2894,4874,1974,1336,3768,1173,3681,1023,4370,4202,3269,2846,4145,4180,2939,35,40,2835,4781,374,4949,4693,2564,633,3618,4752,4439,663,3923,242,2901,3179,3761,1128,2367,3877,3732,2131,1178,3937,3190,656,877,1015,2044,2190,2249,3868,3602,1831,3839,418,3605,2284,1365,444,3065,121,2873,3494,4891,845,3186,201,1191,1698,4087,4904,2471,1928,1677,1917,4881,1904,2079,2754,1380,3766,4216,1880,4638,4014,2596,4512,2030,753,2078,2712,3363,1939,1781,3118,865,4829,3227,3910,4294,1848,2761,4552,1454,197,1221,4916,4337,1166,2011,2374,3309,838,3579,4817,2108,463,2730,2999,4979,1037,3809,801,4124,1388,2857,2273,2439,4827,2693,2968,4167,4840,4386,597,182,2946,3470,744,3656,3478,2555,16,2679,4869,484,3688,1496,1737,3139,1,4683,1686,797,971,2129,1034,4469,4476,3416,4302,2560,1770,3748,1339,3894,3260,76,992,4290,1608,4524,781,2863,2299,959,272,3263,2295,4365,749,2349,1582,2297,443,4027,625,1080,1305,4173,941,3517,3395,2270,4382,2187,3607,2163,1900,844,2854,3701,1005,2547,707,1933,2898,945,3714,1297,2262,4461,4842,1838,3436,3085,474,1585,2354,1095,1837,772,1261,2343,4843,2947,4346,4139,4169,4107,721,4684,1771,4390,353,1977,4744,4097,4019,2551,3340,4926,1764,1575,687,2540,32,3242,560,4351,1346,1890,2577,2921,2708,1579,3277,3070,130,2519,321,1306,2064,2662,4653,2229,256,2341,1033,4331,136,3905,1096,1502,993,4376,2676,3601,64,903,1675,2545,216,4713,3881,2649,1557,783,1492,2268,2706,409,3927,2247,2255,1553,4864,4784,1292,3219,4547,3887,3718,342,4494,4471,3528,1566,1105,3071,2675,4431,4548,4211,1114,2837,1353,1368,4803,3735,2,3882,1713,3484,868,2271,4967,589,361,4783,2060,2567,879,4647,827,2598,1081,2740,4741,4632,966,3274,3794,4606,1231,3974,3550,2527,3700,3398,2240,2566,2455,4030,2277,1422,27,2779,122,2413,1465,4911,1487,1706,2368,3205,3244,2334,3944,3846,849,4853,3824,1715,1780,2635,2285,3576,3024,2209,3874,3795,187,1533,614,3603,771,2852,2991,4707,2174,4247,498,2195,4022,401,785,4854,3746,3257,4350,4981,2630,1687,1809,1603,1332,619,2445,1277,4528,910,4177,3513,1063,613,672,3300,436,1648,153,2931,1625,4391,4952,4893,4288,2571,2608,4320,2320,1816,1006,1596,2820,1562,2984,4306,2582,2725,3815,2691,4608,4319,741,2433,3464,1676,733,4261,108,331,2123,3276,2242,4659,4664,3621,2613,2924,350,4032,4198,3917,2500,575,2860,1417,2908,2869,2897,4232,4739,2969,2363,1668,3112,3059,664,464,2994,3721,3030,1598,94,4206,1845,1952,3422,4447,196,4121,775,3115,1560,1703,2436,3946,415,3658,1334,1783,2430,3711,3130,1511,703,3703,1494,3005,965,4312,4602,4769,2395,3935,4252,928,1308,900,1518,4098,2116,893,275,1708,2309,1651,4094,4340,2767,4694,4448,803,2483,3111,2561,11,92,4815,2421,3127,1403,974,666,4055,3598,1436,4362,4273,2883,2855,1251,118,3258,1839,1340,3113,644,2265,2182,3381,549,4522,1548,2615,2616,1824,608,4816,1645,1628,944,1741,524,19,1808,285,177,2310,1921,4955,2508,279,1532,4437,2326,3557,706,1623,3508,3554,161,4941,3812,253,109,4634,1112,3168,1167,4673,4196,3270,1519,1543,1115,1200,261,3540,876,3716,1069,3391,1719,4402,250,3767,190,2388,4449,1407,421,2799,1111,4385,899,3228,1256,4316,1844,4910,716,658,1863,4956,571,2245,429,1627,4410,2386,3194,3049,679,2805,956,461,2006,2915,676,1323,2456,2287,914,4983,170,896,2548,427,4945,4877,2117,981,1506,2889,4953,139,1641,995,4381,3837,4304,4487,3359,1733,3336,2671,4002,1669,4270,4850,2447,582,1833,1247,650,4152,60,2523,808,1260,165,314,2438,4430,1841,1185,1717,2719,4533,496,2982,1862,4972,3919,1347,4556,3682,4254,1162,1165,1250,3581,411,56,4112,3677,1490,2510,1046,2739,3230,2723,782,1457,183,835,586,4249,2821,72,595,3170,1673,1868,2818,1540,132,2879,1359,4915,192,4279,383,4296,3884,3455,1573,4708,3241,4991,4846,213,2184,3163,856,2645,4433,2628,99,4404,4475,3899,3850,2214,2983,1133,635,3842,3994,2472,2888,2629,4341,788,1565,2664,1514,4325,96,1211,3544,1722,973,4451,2996,4766,3984,2286,2970,1217,3596,4285,979,2062,1213,2444,1593,1959,4203,4607,430,3976,887,2813,3136,3474,351,4971,665,963,1542,3522,3360,3217,2677,2825,1193,3132,1108,8,1985,1907,1446,4529,1098,3989,1643,3672,3570,3284,2622,693,1849,2474,4406,1329,151,4486,3424,1349,3530,3855,4342,4186,4146,3307,1700,3080,1146,3121,2536,1659,4862,3620,3046,2034,3399,4830,3162,4709,1699,3009,1761,1725,943,2246,319,4875,1328,1873,4450,1572,85,1295,2627,1629,1172,267,4680,4481,4646,1558,4132,747,3500,2501,2919,3052,475,4996,252,3597,1433,4166,2636,3245,1721,3433,3980,1647,1188,1989,1649,2419,1634,465,4330,2765,1246,4701,1755,4652,1280,3042,4366,3415,3886,1976,3485,4050,1381,4930,1639,1315,1092,4578,2028,1223,3206,2585,1886,3074,1091,4669,4108,3801,2026,3831,3924,2375,1696,1672,4297,4749,699,1351,313,805,4657,4309,2620,2682,1714,3347,143,4645,4800,1760,1658,4201,13,335,2012,789,907,425,4565,799,1400,3301,821,2871,77,3382,1058,505,1007,440,370,2720,3379,1727,2727,729,1117,2431,3180,1655,2541,4468,1075,1414,1818,2581,1731,1177,1747,123,381,2752,2550,191,3828,49,3657,3412,4062,2121,2701,1389,2794,1140,2167,2930,4482,346,265,4871,2073,4070,1242,1757,339,3647,2210,1100,4204,240,1784,500,3386,3119,4982,855,3731,4615,273,3953,730,3968,2543,1393,991,3495,1853,3342,815,2383,696,3423,1875,921,200,4010,2774,4456,1522,4479,1576,1601,438,254,3092,3167,2934,4923,1580,3626,2052,1189,2451,4217,4906,4164,4384,2312,1832,1216,1663,4189,3250,3426,3765,2881,4938,460,977,1738,2135,4675,315,1086,2311,1035,1397,384,3148,4322,2091,2507,1678,2950,3006,4705,1521,1694,3060,4327,2211,807,2144,3204,1038,3487,2045,1016,4579,755,4718,3055,1243,1843,603,1263,2841,4257,4764,2979,4648,2704,750,4360,2588,3830,1061,3926,565,4051,2748,2703,2670,1301,1017,3058,3991,4725,3617,6,3232,2292,3708,2005,2317,3552,708,4130,2465,1307,3612,3539,526,2948,78,3110,3259,1935,1997,4790,1145,1923,2428,2533,1539,433,2207,3101,3538,2802,3548,2563,2025,3752,1450,4064,2988,4025,1029,397,3100,4710,1036,2899,2912,4195,1821,2127,4526,225,4353,2382,3449,4537,1367,1210,2832,1151,2847,3590,2826,3611,1885,3390,4207,1965,1624,3712,704,4393,4332,2381,3358,3784,3872,4114,3086,632,206,174,3116,2715,3556,3356,4339,2867,1745,4434,989,235,388,4117,1609,4964,244,2589,378,1787,79,4354,536,4665,2448,2546,3810,3577,4514,1661,834,4771,1171,2017,4984,86,2166,88,2475,263,2346,2695,4799,2216,237,2958,4184,186,3955,3775,683,3789,1051,1869,2261,1759,2972,3029,1460,163,1089,2911,2359,3845,997,2690,798,257,2279,4443,2192,2665,2050,3908,2160,2066,1265,1262,1481,269,935,494,3690,4641,4088,2405,1531,2831,1691,2157,3986,621,4235,1497,4480,2975,4047,4535,4001,2651,2666,1586,2102,3262,1883,1920,2165,1640,1229,1119,1442,3287,4419,2401,2100,740,791,4704,3802,538,3504,988,4242,2171,1376,4237,2243,728,82,4598,3526,1468,4577,4721,4352,2306,754,2427,1800,3880,3453,2391,3043,1962,3734,1972,2227,1730,2942,1438,604,1003,2120,2893,1525,112,2489,4427,2088,283,2859,1772,4174,1817,2015,4183,1273,3780,4408,3606,4918,1975,3799,2443,3278,2366,584,2416,185,3335,1137,4692,1103,2520,1594,3327,369,1401,4326,869,2792,4518,872,3646,4367,1391,1949,4763,4672,21,2094,3428,1740,999,4490,2914,762,1932,360,4715,3507,833,922,4985,1789,2823,1942,4987,2758,3334,2112,2842,4396,202,2817,2328,1825,2776,476,3645,1971,2181,2293,4866,2033,284,1027,4041,4759,1143,4194,2553,1408,3201,449,4497,609,4699,2132,3630,4671,334,3793,3445,1464,1202,3442,4081,610,3958,2749,106,2838,3936,4092,2230,3198,1350,4837,1230,3871,3920,2020,4617,2201,2907,1267,3865,642,4127,2204,4165,4008,541,246,3585,3156,1281,3212,209,2289,3760,341,3632,1209,2530,4091,3710,2812,389,3389,2222,3702,4515,2126,793,1864,3582,4782,4255,1509,3560,1320,4970,277,4719,4553,4989,4542,2397,1670,2654,592,1126,1357,3637,158,293,1118,4317,1964,3608,3623,3057,1552,2955,2549,359,4496,1724,2913,146,224,4160,3515,3475,530,4503,2046,3001,891,4778,1077,3131,1951,2392,1394,4527,3266,1652,2418,4405,2118,2276,1570,1294,591,606,93,2940,156,1834,2215,4259,4440,778,400,2603,651,2323,2054,2853,806,892,1692,428,3472,137,3175,514,2115,640,1633,4493,611,2732,345,4263,2461,3272,3385,1980,4640,3235,3380,3754,379,3967,4209,1846,1906,3744,4502,933,2516,622,2688,4780,908,487,1337,1889,1208,3349,3661,2707,3216,2864,2252,3104,767,990,2450,2756,942,4034,2002,2868,295,3822,2486,626,3108,2586,4042,1109,4085,2466,4307,2394,4834,1291,645,2143,4594,4611,4192,2491,2641,4416,4460,4961,1030,4115,1930,1583,3829,3981,4860,3098,452,2998,4336,55,1513,4426,3720,4227,897,1941,698,1032,175,4172,4171,4737,3281,417,2795,4883,4569,1486,1434,4126,2796,2977,1330,1617,435,4735,885,3569,249,3486,4880,3209,336,4379,323,4505,1915,1925,4277,3759,818,2964,970,4199,1887,4506,2646,4567,2481,3912,301,189,3529,863,2141,1982,4730,1835,4931,4137,2815,2514,1212,4435,4654,1857,969,4793,957,1253,3706,3392,4187,662,888,4992,2503,3559,4600,115,1335,2923,3625,2275,3218,2672,2601,4841,587,550,4035,4210,1064,98,3814,1795,3680,1859,2389,455,3501,1967,4697,4903,2109,3088,898,3022,648,3346,2142,2494,3288,2075,1662,4820,543,2485,4067,2657,63,3443,4280,4445,2377,1324,2469,1619,3135,4868,986,3480,3444,3012,2183,2579,1896,22,2213,3153,1720,4824,4175,2335,405,1002,3099,4576,1004,1179,1987,3214,297,4959,2185,4245,3574,1671,1571,1616,3295,1940,2107,4762,2870,3324,467,4574,1008,4612,2358,2965,3435,3911,2785,702,2384,3854,1665,1325,2981,901,3044,135,1284,1973,296,3818,3468,2239,518,4106,4922,1595,431,2734,4129,215,1707,1449,2737,3954,238,1978,3900,3367,777,4785,1448,4161,3210,2594,3473,2578,2208,3796,219,1600,2845,2053,2681,2315,3073,615,3460,2757,4890,508,2780,843,2621,2267,2562,354,3904,39,3546,3644,1797,4043,1361,2233,2694,1042,2700,1779,1156,3956,4344,3331,4624,1950,4858,4999,1504,2373,1318,3421,4788,2110,1405,1144,1547,1895,391,4119,2935,4859,4040,4823,2759,3490,3665,3223,2997,4896,1546,4734,1604,4056,3890,2777,3252,3537,3026,3165,4143,1268,457,3040,2058,3583,3673,1957,3200,3664,3942,3152,2149,787,178,2250,2610,2738,2226,497,2059,4457,1104,3466,759,282,4536,675,4826,4753,1175,4298,4928,4442,3140,3511,932,4986,2593,3835,520,1739,1420,4773,3628,2225,1099,3202,4006,1204,1537,2583,2843,4197,2822,1806,2290,641,2371,1994,1062,437,1131,3652,289,2305,1995,66,4371,4140,3938,4848,67,4061,1257,4726,3134,2978,4564,2669,141,4580,559,2218,2809,3215,2856,4141,1326,4649,4387,3418,1762,3929,2098,4805,3667,3771,1556,3420,380,4968,3838,766,2565,3496,1342,1744,1856,573,127,1043,1479,2900,171,4625,490,4241,2032,2617,3328,4643,2724,2904,1183,173,2269,1386,1842,1056,2920,931,3807,3037,148,3770,2454,3437,304,2650,677,4917,45,4974,1343,2039,3,713,916,585,2080,701,2248,4375,1681,2766,4660,4787,1219,4887,2308,1148,1240,1053,1226,3247,2632,531,2202,4582,2122,3305,4706,180,2274,4892,31,4509,680,4619,3450,940,495,4943,4819,3018,3864,1138,3409,3932,3320,2199,1290,4811,131,2609,918,1423,537,286,4205,4144,4120,2573,2459,773,964,4627,327,2362,1363,2744,2467,639,134,1695,2197,4083,4308,3221,2667,4023,3817,3671,840,3594,80,4571,688,1366,89,4685,53,3786,1855,4500,2572,258,521,3158,337,1040,1498,3821,3321,4128,3296,4182,2770,2687,4812,1799,4678,271,4754,2751,2231,1850,682,962,761,4835,448,113,4168,1311,24,212,236,4801,2798,1296,3197,3109,4284,4082,97,4944,1011,3687,3282,1567,2804,2872,842,2234,1269,1052,1814,4544,1316,4777,3032,2717,4942,2741,230,1597,2736,4631,4958,4905,1912,2493,4601,1199,2787,1094,3971,2944,3122,2539,2154,3176,3806,3375,1379,2303,4462,1811,1206,4407,3264,3907,3619,512,184,674,4913,2492,1632,1790,1693,4148,1991,1421,3322,1237,1927,466,994,3650,554,3790,2647,2851,1786,2698,4318,1666,1499,556,3827,211,3551,2124,3419,1410,1763,1613,4190,2159,116,3715,3520,3966,1559,52,1536,1549,2769,169,1252,983,214,1085,205,2784,3545,3400,4810,4498,2314,564,3451,2840,533,3562,4364,2463,4570,2496,3226,2007,3404,643,867,1660,3737,1282,3246,2875,4855,2791,1826,853,1153,3182,3782,4557,1605,3440,218,3077,2473,2435,1805,4517,1688,1289,1078,939,695,1788,239,1893,902,848,2986,3463,2652,4228,1587,1272,2324,1412,491,3144,303,3755,686,3187,3891,3565,4541,738,737,2241,2331,3649,2477,2128,1430,1369,913,162,3993,1142,347,2605,1424,310,2829,276,2772,2047,1520,1088,2718,3567,154,1823,2291,298,1362,2509,28,4329,3930,243,3970,1312,3374,3476,419,266,4870,4511,4116,862,3950,2801,2029,4501,1025,2425,3000,3181,823,3149,1840,1777,441,349,4077,566,4037,870,4096,3713,2584,2660,670,3017,2992,2212,3523,3939,616,3997,2458,1278,4068,4755,1067,2488,1358,3785,2861,3387,3491,4347,3622,1836,4411,4628,1360,2614,982,2985,2302,3928,4049,1399,2393,4333,4530,4609,2161,395,3067,3972,2612,4937,2877,1123,2105,4521,691,4745,1894,4093,320,4791,1225,4957,469,3973,4585,4997,176,3315,3338,4901,1245,4251,4071,1322,4052,3172,2961,534,355,4271,193,3137,4388,2351,84,4499,2412,3105,1049,2016,1431,690,2532,4642,878,2093,4425,4639,2518,2755,1073,3431,3159,837,4605,4423,1161,4677,2910,1822,2806,3081,1227,4383,3078,2387,4610,4899,2743,659,830,210,3885,2742,3633,1375,1083,2886,1453,2244,2714,1523,2068,3743,386,2696,1181,152,348,179,2369,4742,4925,607,4438,722,2625,727,3275,4691,3369,1851,3267,4377,1966,1197,2339,1527,4110,2482,4908,2902,2602,1228,1186,479,1059,1538,4568,4361,4698,2882,1792,2557,2689,2936,3090,4644,3394,1577,1304,929,1813,1474,4274,671,3164,50,2800,2257,3183,1124,20,3694,4109,2178,3056,4136,4226,2917,2307,4757,3641,2158,667,4214,2153,3064,373,1528,3097,34,453,4921,4873,1152,288,2332,399,4466,4872,1387,4662,2180,1341,745,1510,4053,1390,2684,2022,3588,2922,2106,2347,3481,1614,3696,1626,3371,2971,3341,2350,3025,4720,4101,3329,168,3727,4797,2498,3813,308,203,3014,692,274,3326,3333,4886,1931,1891,2057,2319,4620,561,4368,1406,3536,795,4636,1214,3082,2810,1201,3600,4561,2140,2406,1534,1723,2937,3558,2111,1961,4414,3365,125,3254,396,25,4954,129,3166,4,1746,715,1485,2600,2169,2083,4046,817,946,555,4474,392,552,69,4933,4775,1321,3361,2077,4838,2878,1726,188,1125,393,2063,1815,4946,3519,2954,2119,1882,3207,1654,3534,4478,1068,4592,7,3745,1899,133,1187,4229,4231,3008,220,3308,4000,3572,3211,2891,2464,1776,3316,1736,2558,377,577,4188,3819,3692,2272,4732,3285,2716,1874,3312,2177,3368,3753,4682,2987,3965,3792,1182,3488,2294,2607,1773,1054,3670,4239,1495,2422,1751,987,1705,3106,2576,4807,1459,3447,1911,3471,3239,2830,2733,3896,458,3430,3448,760,1254,3031,4133,4295,2426,4282,3666,551,3640,2505,4454,4060,2699,46,3304,1866,1026,593,2927,4847,2484,2065,947,4293,725,4994,2788,2360,3521,3949,489,2895,596,1418,3154,2844,3893,3243,4934,3087,2658,2957,3185,1913,4746,1829,1711,3662,280,3726,2221,3352,3053,2136,3498,4012,515,4039,1752,1483,875,1775,2731,1110,2370,1710,1561,553,1728,3161,3934,3648,3062,3378,1657,1174,1484,1667,654,2259,4674,4789,4558,1224,1778,4738,567,1435,4549,4153,3636,4157,2396,4102,4003,4380,743,562,3007,4758,2018,1642,471,1160,3279,905,2849,2344,2114,3427,873,3411,2967,3222,3236,4212,937,3699,4849,4222,1222,4489,3960,2655,3407,2819,2372,2638,1679,630,864,4583,1914,3697,1461,3401,2966,1564,2256,4545,3541,1071,657,4356,1979,1732,394,1234,1371,2848,4253,4513,601,4441,568,3553,4876,3931,3147,2865,2070,3169,1515,1370,3128,1505,4495,4015,3804,742,4394,3402,2137,2051,4818,655,958,2390,2407,4966,4158,4477,712,1271,1107,4947,1881,2941,1348,3843,1990,4099,4879,3405,58,2880,4696,228,4272,2887,3862,4086,4690,3357,4898,4852,3676,4856,164,4700,2049,1718,623,227,811,2797,4907,140,2084,4559,2639,4378,3774,4733,3859,4976,1132,2296,4724,2529,717,1101,1919,1555,1750,858,1621,4421,816,3293,600,1463,4630,4551,3913,3848,2506,247,4230,4977,3479,4465,4863,4009,287,4483,3343,2726,2623,4349,4058,4459,661,2200,2353,4596,4075,3675,3016,3961,841,4792,618,3642,975,594,828,3075,516,1796,2095,4656,3983,4510,4597,1288,502,2236,1279,3941,503,4473,2768,1637,2850,4072,416,1716,3895,472,1903,1753,251,3003,4142,894,2322,2517,3054,822,3778,4635,4219,144,2313,4668,861,3825,3354,4315,36,446,4488,3777,4712,3286,1184,1377,3353,3096,3145,517,2155,1338,736,4301,3990,12,1443,3851,4492,3933,2031,4865,3655,3512,4806,3987,1801,149,3345,1134,2282,4151,2814,4020,3914,4313,2648,1529,3757,2903,938,3779,1163,2659,1878,2763,1198,48,2186,3151,2786,646,3921,344,3438,2298,2521,2223,574,2778,2858,2537,2417,2263,2932,3869,3384,3477,3686,1009,1235,3999,2134,1986,4587,4444,330,1631,985,2021,984,4809,2929,4193,4722,1041,3015,4218,726,4909,159,3020,3916,631,1356,1622,1689,3533,4794,4796,1802,1611,2595,311,2125,1476,3945,4884,1535,2626,3800,2512,4063,1888,1902,1084,2569,2414,2340,3820,2524,4589,4418,1478,1102,3940,3408,540,819,1517,794,967,1635,4429,138,724,451,4031,3083,4470,4105,3975,2019,3783,385,3733,4525,1022,4676,3021,4409,104,4621,915,3240,3693,3634,4149,2781,3388,3683,563,3318,1310,2980,1028,3133,2925,2460,2071,3875,812,3948,312,4357,3178,4531,1827,2280,4995,1411,1910,4424,3310,1120,4748,3072,4554,2938,3150,501,4867,198,2834,1963,2568,2316,829,2592,4147,2554,700,3376,2580,2191,1236,1819,3079,91,300,4687,4029,1001,4563,532,2952,480,4590,1618,4616,4939,3723,3325,4131,539,2254,1526,2885,3114,4104,3120,1993,2087,3051,2408,3631,1455,4924,2953,4223,4729,2479,1936,1656,3068,2653,1916,1958,1354,2928,3066,2056,2266,535,960,317,2790,3549,2449,3465,2661,3294,513,3674,3659,4507,2892,4651,375,1352,3350,3251,1674,3196,1702,3888,4633,3689,3313,831,629,3225,569,3527,2542,2916,3410,3303,839,3542,2355,3268,3669,2918,4076,4033,602,2525,2773,871,1445,1591,3117,909,746,4914,2342,3317,1748,3863,4287,1607,1861,3906,1428,3709,4090,3510,1082,248,3663,14,545,3319,3613,1472,2674,2235,4988,4828,65,4973,3160,2076,57,1396,2522,390,408,1205,1541,2721,3832,1416,4078,4655,697,3280,634,904,4520,366,709,4595,3660,3446,2072,1097,3903,4523,1860,2173,2402,3811,3351,948,2090,4436,4491,1803,1897,3344,790,1014,4629,2729,4389,978,4250,4650,18,4929,1398,3593,1010,4723,1385,4398,544,426,3985,1155,1203,4048,4912,424,4178,2816,599,4095,1317,3982,2147,2364,4560,3383,961,4395,3861,119,927,2188,3195,4963,166,3199,3592,4776,1215,4802,826,1996,1758,2956,3010,4767,71,2325,580,4243,4534,3524,2086,1402,1345,2348,2037,1065,4786,2162,1550,2896,2933,4504,2504,1644,1544,2866,194,4714,1945,4935,1427,1524,3208,15,2862,2973,1709,42,447,854,4573,4919,669,1937,3458,636,590,1854,950,1501,1470,2321,4485,101,3413,2556,3023,3355,689,4604,529,4588,4185,442,4543,1767,2170,3586,3518,506,2789,4286,1258,3803,2535,1275,3889,2085,779,4808,1516,714,4681,3337,1754,3231,2399];